#ifndef TREE_H__
#define TREE_H__

//#define ElemType char      //存储元素类型

typedef struct BinaryTreeNode
{
	char data;
	struct BinaryTreeNode *leftchild, *rightchild;
} BinaryTreeNode;

typedef struct BinaryTree
{
	BinaryTreeNode *root;
	char refvalue; // stop flag
} BinaryTree;

void Init(BinaryTree *bt, char ref); //初始化

void Create1(BinaryTree *bt, char **strp); //创建二叉树方法1
void Create1_(BinaryTree *bt, BinaryTreeNode **root, char **strp);

void Create2(BinaryTree *bt, char **strp); //创建二叉树方法2：返回值方式
BinaryTreeNode *Create2_(BinaryTree *bt, char **strp);

void PreOrder(BinaryTree *); //前序遍历
void PreOrder_(BinaryTreeNode *);

void InOrder(BinaryTree *); //中序遍历
void InOrder_(BinaryTreeNode *);

void PostOrder(BinaryTree *); //后序遍历
void PostOrder_(BinaryTreeNode *);

void LevelOrder(BinaryTreeNode *); //层次遍历

int Size(BinaryTree *);
int Size_(BinaryTreeNode *); //求二叉树的结点个数:左子树结点个数+右子树结点个数+1

int Height(BinaryTreeNode *); //求二叉树的高度:max{左子树高度,右子树高度}+1

BinaryTreeNode *Search(BinaryTreeNode *, char key); //查找某个结点：比较根-->比较根的左子树-->比较根的右子树

BinaryTreeNode *Parent(BinaryTreeNode *, BinaryTreeNode *); //第一个参数为树根，第二个参数为要查找的结点

BinaryTreeNode *LeftChild(BinaryTreeNode *p); //求左孩子

BinaryTreeNode *RightChild(BinaryTreeNode *p); //求右孩子

int Empty(BinaryTree *); //判断一棵树是否为空

void Copy(BinaryTreeNode *, BinaryTreeNode **); //拷贝一棵树

void Clear(BinaryTreeNode **); //销毁一棵树

//==============================================================
//非递归的遍历方式

int _PreOrder(BinaryTreeNode *);   //非递归前序遍历
int _PreOrder2(BinaryTreeNode *node);

int _InOrder(BinaryTreeNode *);   //非递归中序遍历

void _PostOrder(BinaryTreeNode *);

#endif